You are given a
positive integer n. Let us consider
set A of fractions x/y where 0 ≤ x / y ≤ 1, y ≤ n and the maximum common divisor of x and y is 1.
For example n = 5. Set A in increasing order
consists of elements
0/1; 1/5; 1/4; 1/3;
2/5; 1/2; 3/5; 2/3; 3/4; 4/5; 1/1
Your task is to
find the i-th smallest fraction in
set A.
Input. The first line contains the number of testcases t (t
≤ 15). The first line of each testcase contains numbers n and m (n ≤ 5000, m ≤ 10000). The next m
lines contain one question each.
Output. For each testcase, you should output m lines which are the answers to the m questions.
Sample Input
1
5 4
1
3
5
8
Sample Output
0/1
1/4
2/5
2/3
рекурсия – последовательность Фарея
Для каждого теста
сгенерируем последовательность Фарея Fn. Далее за O(1) выводим i-ую дробь.
Реализация алгоритма
#include <stdio.h>
#define MAX 5000*5000/10*4
int tests, i, n, m, pos;
int a, b, c, d, p, q;
int x[MAX], y[MAX];
int main(void)
{
scanf("%d",&tests);
while(tests--)
{
scanf("%d %d",&n,&m);
x[1] = a = 0; y[1]
= b = 1; // 0 / 1
x[2] = c = 1; y[2]
= d = n; // 1 / n
pos = 3;
while(c != 1|| d != 1) //
till we reach 1/1
{
x[pos] = p = c *
((n + b) / d) - a;
y[pos] = q = d *
((n + b) / d) - b;
pos++;
a = c; b = d;
c = p; d = q;
}
while(m--)
{
scanf("%d",&i);
printf("%d/%d\n",x[i],y[i]);
}
}
return 0;
}